#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

vector<int> smallestRange(vector<vector<int>>& nums) {
    int n = nums.size();
    unordered_map<int, vector<int>> a;
    int nmin = INT_MAX, nmax = INT_MIN;
    for (int i = 0; i < n; i++)
        for (auto x : nums[i])
        {
            a[x].push_back(i);
            nmin = min(nmin, x);
            nmax = max(nmax, x);
        }

    vector<int> st(n);
    int count = 0;
    int l = nmin, r = nmin - 1;
    int begin = nmin, end = nmax;

    while (r < nmax)
    {
        r++;
        if (a.count(r))
            for (auto x : a[r])
            {
                st[x]++;
                if (st[x] == 1)
                    count++;
            }

        while (count == n)
        {
            if (r - l < end - begin)
            {
                begin = l;
                end = r;
            }
            if (a.count(l))
                for (auto x : a[l])
                {
                    st[x]--;
                    if (st[x] == 0)
                        count--;
                }
            l++;
        }
    }

    return { begin,end };
}